
goog.provide('jsmeta.parser');
goog.require('jsmeta.parser.recursive');

function Parser() {
  this.id = ++Parser.parseNodeID;
}

Parser.debugLineNumber = 0;
Parser.parseNodeID = 0;
Parser.globalDebug = false;
      Parser.globalDebug = true;

Parser.prototype.interpret = function(ctx) {
  throw 'run finished';
}

Parser.debugPrint = function(text) {
  document.body.innerHTML += text;
}

Parser.debugPrintLine = function(line) {
  Parser.debugPrint('<br>' + ++Parser.debugLineNumber + ' - ' + line);
  if ((Parser.debugLineNumber % 2) == 0)
    //setTimeout(300,function(){window.scroll(0,888988)});
    window.scroll(0,888988);
  //alert(line);
}

Parser.debugBoldLine = function(line) {
  Parser.debugPrintLine('<strong>' + line + '</strong>');
  //alert(line);
}

Parser.prototype.run = Parser.globalDebug
  ? function(ctx) {
  var next = this, last = this;
  var start = new Date();
  try {
    for (;;) {
      next = next.interpret(ctx);
      if (next && next === last.caller) {
        Parser.debugPrint(last.outcome
          ? '<font color="green"> - SUCCESS</font>'
          : '<font color="red"> - FAILURE</font>'
        );
      }
      if(next) {
        Parser.debugPrintLine(next.id + ' - offset ' + ctx.offset + ' : phase ' + next.phase + ' start: ' + next.start + ' : ' + next.debugParse(ctx));
      }
      if(next)last = next;
    }
  } catch (e) {
    if (last===this) { // the parse program completed
    //if (typeof(next)=='undefined') { // the parse program completed
      Parser.debugBoldLine('parse ' + (this.outcome ? 'succeeded' : 'failed') + " at offset " + ctx.offset + " and it was " + (this.done ? 'done' : 'not done'));
      Parser.debugBoldLine('duration: ' + (new Date() - start) + ' ms');
      var item_count = 0; for(var a in ctx.memo)++item_count;
      Parser.debugBoldLine('memo items: ' + item_count);
      return this;
    } else {
      Parser.debugBoldLine('Error in ' + last + ' at phase ' + last.phase + ' : ' + e);
      throw e;
    }
  }
} : function(ctx) {
  var next = this;
  var start = new Date();
  try {
    for (;;)
      next = next.interpret(ctx);
  } catch (e) {
    if (typeof(next)=='undefined') { // the parse program completed
      Parser.debugBoldLine('parse ' + (this.outcome ? 'succeeded' : 'failed') + " at offset " + ctx.offset + " and it was " + (this.done ? 'done' : 'not done'));
      Parser.debugBoldLine('duration: ' + (new Date() - start) + ' ms');
      return this;
    } else {
      Parser.debugBoldLine('Error in ' + last + ' at phase ' + last.phase + ' : ' + e);
      throw e;
    }
  }
}

Parser.prototype.replaceCallee = function(callee) {
  this.pattern = callee;
}

Parser.prototype.clone = function() {
  return new (this.constructor);
}

Parser.prototype.isPure = function(ctx) {
  return true;
}

Parser.prototype.isRecursive = function(ctx) {
  return false;
}

Parser.throwRE = function() {
  throw 'recursive';
}

Parser.doneRE = function() {
  return this.cachedRE;
}

Parser.prototype.throwRE = function(ctx) {
  this.emitRE = Parser.throwRE;
}

Parser.prototype.doneRE = function(ctx) {
  this.emitRE = Parser.doneRE;
}

Parser.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : (this.debugParseCached = this.constructor.toString().match(/^function Parser_(\w+)/)[1]);
}

var HI_SURROGATE_START = 0xD800;
var HI_SURROGATE_END = 0xDBFF;
var LO_SURROGATE_START = 0xDC00;
var D65536 = 0x10000;
var LEAD_OFFSET = HI_SURROGATE_START - (D65536 >> 10);
var SURROGATE_OFFSET = D65536 - (HI_SURROGATE_START << 10) - LO_SURROGATE_START;

function ParseContext(inputString) {
  this.input = inputString;
  this.offset = 0;
  var length = this.utf16Length = inputString.length;
  var chars = [];
  var count = 0;
  for (var offset = 0; offset < length; ++offset) {
    var code = inputString.charCodeAt(offset);
    chars[count++] = HI_SURROGATE_START <= code && code <= HI_SURROGATE_END && offset < length
      ? ((code - HI_SURROGATE_START) << 10) + (str[++offset] - LO_SURROGATE_START) + D65536
      : code;
  }
  this.length = count;
  this.last = count - 1;
  this.unicodes = chars;
  this.cutlevels = {};
  this.memo = {};
}

ParseContext.prototype.nodeResult = function(pattern, result) {
  var o = pattern = pattern.caller.left;
  while (!(pattern instanceof Parser_Node)) {
    pattern = pattern.caller;
  }
  return pattern.result = typeof(result) != 'undefined' ? result : o.result;
}

ParseContext.prototype.text = function(pattern) {
  return this.input.substring(pattern.caller.left.start, this.offset);
}

ParseContext.prototype.textResult = function(pattern, nodeType) {
  return this.nodeResult(pattern, {
    "text" : this.text(pattern),
    "type" : nodeType
  });
}

function Parser_End() {
  Parser.call(this, arguments);
}
goog.inherits(Parser_End, Parser);

Parser_End.prototype.interpret = function(ctx) {
  this.start = ctx.offset;
  if (ctx.offset == ctx.length)
    this.done = this.outcome = true;
  return this.caller;
}

Parser_End.prototype.emitRE = function(ctx) {
  this.doneRE();
  return this.cachedRE = '$';
}

function Parser_Empty() {
  Parser.call(this, arguments);
}
goog.inherits(Parser_Empty, Parser);

Parser_Empty.prototype.interpret = function(ctx) {
  this.start = ctx.offset;
  this.done = this.outcome = true;
  return this.caller;
}

Parser_Empty.prototype.emitRE = function(ctx) {
  return '(?:)';
}

function Parser_Literal(literalString, unicodes) {
  Parser.call(this, arguments);
  this.literalString = literalString;
  this.unicodes = unicodes || new ParseContext(literalString).unicodes;
}
goog.inherits(Parser_Literal, Parser);

Parser_Literal.prototype.interpret = function(ctx) {
  var unicodes_target = this.unicodes;
  var unicodes_input = ctx.unicodes;
  var start = this.start = ctx.offset;
  for (var i = 0, j = unicodes_target.length; i < j; ++i) {
    if (unicodes_target[i] != unicodes_input[start + i]) {
      return this.caller;
    }
  }
  this.outcome = true;
  this.done = true;
  ctx.offset += unicodes_target.length;
  return this.caller;
}

Parser_Literal.prototype.clone = function() {
  return new Parser_Literal(this.literalString, this.unicodes);
}

Parser_Literal.prototype.emitRE = function(ctx) {
  this.doneRE();
  return this.RE = XRegExp.escape(this.literalString);
}

Parser_Literal.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Literal(\'' + this.literalString + '\')');
}

function Parser_Both(left, right) {
  Parser.call(this, arguments);
  this.left = left;
  this.right = right;
  this.phase = 0;
}
goog.inherits(Parser_Both, Parser);

Parser_Both.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.phase = 1;
      this.start = ctx.offset;
      this.left = this.left.clone();
      this.left.caller = this;
      return this.left;
    case 1:
      if (this.left.outcome) {
        this.phase = 2;
        this.right = this.right.clone();
        this.right.caller = this;
        return this.right;
      }
      this.outcome = false;
      return this.caller;
    case 2:
      if (this.right.outcome) {
        this.outcome = true;
        if (!(this.done = this.left.done && this.right.done))
          this.phase = 3;
        return this.caller;
      }
      if (!this.left.done) {
        ctx.offset = this.start;
        this.phase = 1;
        return this.left;
      }
      this.outcome = false;
      return this.caller;
    case 3:
      if (this.right.done) {
        if (this.left.done) {
          this.outcome = false;
          return this.caller;
        }
        this.phase = 1;
        return this.left;
      }
      this.phase = 2;
      ctx.offset = this.right.start;
      return this.right;
  }
}

Parser_Both.prototype.replaceCallee = function(callee) {
  switch (this.phase) {
    case 0:
    case 1:
      this.left = callee;
      break;
    case 2:
      this.right = callee;
  }
}

Parser_Both.prototype.clone = function() {
  return new Parser_Both(this.left, this.right);
}

Parser_Both.prototype.isPure = function(ctx) {
  return this.left.isPure(ctx) && this.right.isPure(ctx);
}

Parser_Both.prototype.isRecursive = function(ctx) {
  return !(this.left.isRecursive(ctx) || this.right.isRecursive(ctx));
}

Parser_Both.prototype.emitRE = function(ctx) {
  this.doneRE();
  return this.cachedRE = this.left.emitRE(ctx) + this.right.emitRE(ctx);
}

Parser_Both.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Both(' + this.left.debugParse(ctx) + ',' + this.right.debugParse(ctx) + ')');
}

function Parser_Either(left, right) {
  Parser.call(this, arguments);
  this.left = left;
  this.right = right;
  this.phase = 0;
}
goog.inherits(Parser_Either, Parser);

Parser_Either.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.phase = 1;
      this.start = ctx.offset;
      this.left = this.left.clone();
      this.left.caller = this;
      return this.left;
    case 1:
      if (this.left.outcome) {
        this.outcome = true;
        this.done = false;
        this.phase = this.left.done ? 2 : 3;
        return this.caller;
      }
      ctx.offset = this.start;
    case 2:
      this.phase = 4;
      this.right = this.right.clone();
      this.right.caller = this;
      return this.right;
    case 3:
      this.phase = 1;
      return this.left;
    case 4:
      if ((this.outcome = this.right.outcome) && !(this.done = this.right.done))
          this.phase = 5;
      return this.caller;
    case 5:
      this.phase = 4;
      return this.right;
  }
}

Parser_Either.prototype.replaceCallee = function(callee) {
  switch (this.phase) {
    case 0:
    case 1:
      this.left = callee;
      break;
    case 2:
    case 3:
    case 4:
      this.right = callee;
  }
}

Parser_Either.prototype.clone = function() {
  return new Parser_Either(this.left, this.right);
}

Parser_Either.prototype.isPure = function(ctx) {
  return this.left.isPure(ctx) && this.right.isPure(ctx);
}

Parser_Either.prototype.isRecursive = function(ctx) {
  return !(this.left.isRecursive(ctx) || this.right.isRecursive(ctx));
}

Parser_Either.prototype.emitRE = function(ctx) {
  this.doneRE();
  return this.cachedRE = '(?:(?:' + this.left.emitRE(ctx) + ')|(?:' + this.right.emitRE(ctx) + '))';
}

Parser_Either.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Either(' + this.left.debugParse(ctx) + ',' + this.right.debugParse(ctx) + ')');
}

function Parser_Repeat(pattern, min, max) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  this.min = min;
  this.max = max == -1 ? 1/0 : max;
  this.phase = 0;
}
goog.inherits(Parser_Repeat, Parser);

Parser_Repeat.prototype.interpret = function(ctx) {
  var acts = this.acts,
      last = this.last;
  switch (this.phase) {
    case 0:
    this.start = ctx.offset;
    this.acts = [last = this.last = this.pattern.clone()];
    last.caller = this;
    this.phase = 1;
    return last;
    
    case 1:
      if (!last.outcome || ctx.offset >= ctx.length || acts.length == this.max) {
        if (!last.outcome) {
          ctx.offset = last.start;
          acts.pop();
        }
        if (acts.length >= this.min) {
          this.outcome = true;
          this.phase = 2;
        } else {
          this.outcome = false;
        }
        return this.caller;
      } else {
        if (ctx.offset < ctx.length) {
          acts.push(last = this.last = this.pattern.clone());
          last.caller = this;
          return last;
        }
      }
    
    case 2:
      if (!last.done) {
        ctx.offset = last.start;
        this.phase = 1;
        return last;
      }
      last = acts.pop();
      if (acts.length >= this.min) {
        this.outcome = true;
        ctx.offset = last.start;
      } else {
        this.outcome = false;
      }
      return this.caller;
  }
}

Parser_Repeat.prototype.replaceCallee = function(callee) {
  this.acts.pop();
  this.acts.push(this.last = callee);
}

Parser_Repeat.prototype.clone = function() {
  return new Parser_Repeat(this.pattern, this.min, this.max);
}

Parser_Repeat.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Repeat.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

Parser_Repeat.prototype.emitRE = function(ctx) {
  this.doneRE();
  if (this.max > 1000000000) {
    switch (this.min) {
      case 0:
        return this.cachedRE = '(?:' + this.pattern.emitRE(ctx) + ')*';
      case 1:
        return this.cachedRE = '(?:' + this.pattern.emitRE(ctx) + ')+';
      default:
        var result = this.pattern.emitRE(ctx);
        return this.cachedRE = '(?:' + result + '){' + this.min + '}(?:' + result + ')*';
    }
  } else {
    return this.cachedRE = '(?:' + this.pattern.emitRE(ctx) + '){' + this.min + ',' + this.max + '}';
  }
}

Parser_Repeat.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Repeat(' + this.pattern.debugParse(ctx) + ',' + this.min + ',' + this.max + ')');
}

function Parser_Final(pattern) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  pattern.caller = this;
  this.phase = 0;
}
goog.inherits(Parser_Final, Parser);

Parser_Final.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      this.done = true;
      this.outcome = this.pattern.outcome;
      return this.caller;
  }
}

Parser_Final.prototype.clone = function() {
  return new Parser_Final(this.pattern);
}

Parser_Final.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Final.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

Parser_Final.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Final(' + this.pattern.debugParse(ctx) + ')');
}

function Parser_Not(pattern) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  pattern.caller = this;
  this.phase = 0;
}
goog.inherits(Parser_Not, Parser);

Parser_Not.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      this.done = true;
      if (!(this.outcome = !this.pattern.outcome))
        ctx.offset = this.start;
      return this.caller;
  }
}

Parser_Not.prototype.clone = function() {
  return new Parser_Not(this.pattern);
}

Parser_Not.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Not.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

Parser_Not.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Not(' + this.pattern.debugParse(ctx) + ')');
}

function Parser_Lookahead(pattern) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  pattern.caller = this;
  this.phase = 0;
}
goog.inherits(Parser_Lookahead, Parser);

Parser_Lookahead.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      this.done = true;
      if (this.outcome = this.pattern.outcome)
        ctx.offset = this.start;
      return this.caller;
  }
}

Parser_Lookahead.prototype.clone = function() {
  return new Parser_Lookahead(this.pattern);
}

Parser_Lookahead.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Lookahead.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

Parser_Lookahead.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('Lookahead(' + this.pattern.debugParse(ctx) + ')');
}

function Parser_Cutlevel(pattern, level) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  this.phase = 0;
  this.level = level;
}
goog.inherits(Parser_Cutlevel, Parser);

Parser_Cutlevel.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      ctx.cutlevels[this.level] = this;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      this.done = this.pattern.done;
      this.outcome = this.pattern.outcome;
      return this.caller;
    case 2:
      this.outcome = false;
      return this.caller;
  }
}

Parser_Cutlevel.prototype.clone = function() {
  return new Parser_Cutlevel(this.pattern, this.level);
}

Parser_Cutlevel.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Cutlevel.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

function Parser_Cutpoint(pattern, level) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  this.phase = 0;
  this.level = level;
}
goog.inherits(Parser_Cutpoint, Parser);

Parser_Cutpoint.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      if (!(this.done = this.pattern.done))
        this.phase = 2;
      if (!(this.outcome = this.pattern.outcome)) {
        var cut_destination = ctx[this.level];
        cut_destination.phase = 2;
        return cut_destination;
      }
      return this.caller;
    case 2:
      this.phase = 1;
      return this.pattern;
  }
}

Parser_Cutpoint.prototype.clone = function() {
  return new Parser_Cutpoint(this.pattern, this.level);
}

Parser_Cutpoint.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Cutpoint.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}

function Parser_RuleCall(ruleName) {
  Parser.call(this, arguments);
  this.ruleName = ruleName;
  this.phase = 0;
}
goog.inherits(Parser_RuleCall, Parser);

Parser_RuleCall.prototype.interpret = function(ctx) {
  var memo = ctx.memo, item;
  switch (this.phase) {
    case 0:
      callKey = this.ruleName + ctx.offset;
      if ((item = memo[ callKey ]) && (item.done || !item.outcome)) {
        this.outcome = item.outcome;
        this.done = true;
        ctx.offset = item.end;
        return this.caller;
      } else {
        memo[ callKey ] = this;
      }
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = ctx.grammar.rules[this.ruleName].clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      if (!(this.done = this.pattern.done))
        this.phase = 2;
      if (this.outcome = this.pattern.outcome)
        this.end = ctx.offset;
      return this.caller;
    case 2:
      this.phase = 1;
      return this.pattern;
  }
}

Parser_RuleCall.prototype.interpret = interpret_recursiveRuleCall;

Parser_RuleCall.prototype.clone = function() {
  var ruleCall = new Parser_RuleCall(this.ruleName);
  if (this.isRecursive)
    ruleCall.interpret = this.interpret;
  return ruleCall;
}

Parser_RuleCall.prototype.isPure = function(ctx) {
  if (ctx.purityRules[this.ruleName])
    return true;
  ctx.purityRules[this.ruleName] = true;
  return ctx.rules[this.ruleName].isPure(ctx);
}

Parser_RuleCall.prototype.isRecursive = function(ctx) {
  if (ctx.recursionRules[this.ruleName])
    return true;
  ctx.recursionRules[this.ruleName] = true;
  return ctx.rules[this.ruleName].isRecursive(ctx);
}

Parser_RuleCall.prototype.debugParse = function(ctx) {
  return this.debugParseCached ? this.debugParseCached : ('RuleCall("' + this.ruleName + '")');
}

function Parser_Callback(closure, contextClosure, argsClosure) {
  Parser.call(this, arguments);
  this.closure = closure;
  this.contextClosure = contextClosure || true;
  this.argsClosure = argsClosure || true;
}
goog.inherits(Parser_Callback, Parser);

Parser_Callback.prototype.interpret = function(ctx) {
  var context = this.contextClosure instanceof Function ? this.contextClosure(ctx) : this;
  var args = this.argsClosure instanceof Function ? this.argsClosure(ctx) : [ctx];
  this.start = ctx.offset;
  this.closure.apply(context, args);
  this.outcome = this.done = true;
  return this.caller;
}

Parser_Callback.prototype.clone = function() {
  return new Parser_Callback(this.closure, this.contextClosure, this.argsClosure);
}

Parser_Callback.prototype.isPure = function(ctx) {
  return false;
}

Parser_Callback.prototype.isRecursive = function(ctx) {
  return false;
}

function Parser_Node(pattern, props) {
  Parser.call(this, arguments);
  this.pattern = pattern;
  this.props = props;
  this.phase = 0;
}
goog.inherits(Parser_Node, Parser);

Parser_Node.prototype.interpret = function(ctx) {
  switch (this.phase) {
    case 0:
      this.start = ctx.offset;
      this.phase = 1;
      this.pattern = this.pattern.clone();
      this.pattern.caller = this;
      return this.pattern;
    case 1:
      if (!(this.done = this.pattern.done))
        this.phase = 2;
      this.outcome = this.pattern.outcome;
      return this.caller;
    case 2:
      this.phase = 1;
      return this.pattern;
  }
}

Parser_Node.prototype.clone = function() {
  // TODO: come up with a scheme to clone props deeply/properly
  return new Parser_Node(this.pattern, this.props);
}

Parser_Node.prototype.isPure = function(ctx) {
  return this.pattern.isPure(ctx);
}

Parser_Node.prototype.isRecursive = function(ctx) {
  return this.pattern.isRecursive(ctx);
}
